# -*- coding: utf-8 -*-
'''
@author: Ricardo Faria 6315 e Luís Freitas 5602
@date: 8 abril de 2013
Classe que permite criar um obtecto Merge
'''
import sys
import math
'''
Classe que permite criar um objeto da classe merge
'''
class Merge:
    
    def __init__(self, A):
        '''
        construtor da classe
        @param A: Lista a receber pelo construtor
        '''
        self.A = A

    def merge(self, p, q, r):
        '''
        Metodo merge que recebe como parametro uma lista, p q e r que sao indices
        @param p: posicao inicial
        @param r: ultima posicao
        @param q: calculado a partir de [(p+r)/2]
        O merge e um metodo auxiliar que efectua um procedimento de agregaçao
        utiliza uma tabela unidimensional
        '''
        n1 = q - p + 1
        n2 = r - q
        L = [1 for x in range(n1+1)]
        R = [1 for x in range(n2+1)]
                    
        for i in range(n1):
            L[i] = self.A[p + i]

        for j in range(n2):
            R[j] = self.A[q + j+1]
            
        L[n1] = (sys.maxint)
        R[n2] = (sys.maxint)
            
        i = 0
        j = 0
        for k in range(p, r+1):
            if L[i] <= R[j]:
                self.A[k] = L[i]
                i = i + 1
            else:
                self.A[k] = R[j]
                j = j + 1
    
    def merge_sort(self, p, r):
        '''
        Metodo reponsavel por organizar a lista recorrendo a ele proprio e ao merge
        @param p: Posicao inicial
        @param r: posicao final
        '''
        if p < r:
            q = (int(math.floor((p+r)/2)))
            self.merge_sort(p,q)
            self.merge_sort(q+1,r)
            self.merge(p, q, r)
        
